//
// Created by 刘振舟 on 2024/3/18.
//
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
    int **data;
    int size;
    int capacity;
} List;


List *createList() {
    List *list = (List *) malloc(sizeof(List));
    list->data = (int **) malloc(16 * sizeof(int *));
    list->size = 0;
    list->capacity = 16;
    return list;
}

void pushBack(List *list, int *arr) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->data = (int **) realloc(list->data, list->capacity * sizeof(int *));
    }
    list->data[list->size++] = arr;
}

void backtrack(int *nums, int numsSize, int *track, int *used, List *res, int trackSize) {
    if (trackSize == numsSize) {
        int *newTrack = (int *) malloc(numsSize * sizeof(int));
        memcpy(newTrack, track, trackSize * sizeof(int));
        pushBack(res, newTrack);
        return;
    }
    for (int i = 0; i < numsSize; ++i) {
        if (used[i] == 1) {
            continue;
        }
        used[i] = 1;
        track[trackSize] = nums[i];
        backtrack(nums, numsSize, track, used, res, trackSize + 1);
        used[i] = 0;
    }
}

int **permute(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    List *res = createList();
    int *track = (int *) malloc(numsSize * sizeof(int));
    int *used = (int *) malloc(numsSize * sizeof(int));
    memset(used, 0, numsSize * sizeof(int));
    backtrack(nums, numsSize, track, used, res, 0);

    *returnSize = res->size;
    *returnColumnSizes = (int *) malloc(res->size * sizeof(int));
    for (int i = 0; i < res->size; ++i) {
        // []运算符优先级比*优先级高
        (*returnColumnSizes)[i] = numsSize;
    }
    return res->data;
}

/*int main() {
    int nums[] = {1, 2, 3};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;
    int *returnColumnSizes;
    int **result = permute(nums, numsSize, &returnSize, &returnColumnSizes);

    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
    }

    return 0;
}*/

typedef struct {
    char ***data;
    int size;
    int capacity;
} Char2DList;


Char2DList *createChar2DList() {
    Char2DList *list = (Char2DList *) malloc(sizeof(Char2DList));
    list->data = (char ***) malloc(8 * sizeof(char **));
    list->size = 0;
    list->capacity = 8;
    return list;
}


void pushBackChar2D(Char2DList *list, char **board, int n) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->data = (char ***) realloc(list->data, list->capacity * sizeof(char **));
    }
    char **newBoard = (char **) malloc(n * sizeof(char *));
    for (int i = 0; i < n; ++i) {
        newBoard[i] = (char *) malloc((n + 1) * sizeof(char));
        for (int j = 0; j < n; ++j) {
            newBoard[i][j] = board[i][j];
        }
        newBoard[i][n] = 0;
    }
    list->data[list->size++] = newBoard;
}

int isValid(char **board, int row, int col, int n) {
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == 'Q') {
            return 0;
        }
    }

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 'Q') {
            return 0;
        }
    }

    for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
        if (board[i][j] == 'Q') {
            return 0;
        }
    }
    return 1;
}

void backtrackNQueens(char **board, int row, Char2DList *res, int n) {
    if (row == n) {
        pushBackChar2D(res, board, n);
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (!isValid(board, row, col, n)) {
            continue;
        }
        board[row][col] = 'Q';
        backtrackNQueens(board, row + 1, res, n);
        board[row][col] = '.';
    }
}


char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes) {
    char **board = (char **) malloc(n * sizeof(char *));
    for (int i = 0; i < n; ++i) {
        board[i] = (char *) malloc(sizeof(char) * n);
        memset(board[i], '.', sizeof(char) * n);
    }

    Char2DList *res = createChar2DList();
    backtrackNQueens(board, 0, res, n);
    *returnSize = res->size;
    *returnColumnSizes = malloc(res->size * sizeof(int *));
    for (int i = 0; i < res->size; ++i) {
        (*returnColumnSizes)[i] = n;
    }
    return res->data;
}


void printResult(char ***result, int size, int n) {
    for (int i = 0; i < size; ++i) {
        printf("============ The %dnth result =============\n%", i + 1);
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                printf("%c ", result[i][j][k]);
            }
            printf("\n");
        }
    }
}

/*int main() {
    int returnSize;
    int *returnColumnSizes;
    char ***res = solveNQueens(8, &returnSize, &returnColumnSizes);
    printResult(res, returnSize, 8);
    return 0;
}*/



void backtrackNQueensTotal(char **board, int row, int n, int *count) {
    if (row == n) {
        // * 和自增运算符具有相同优先级，同时存在时按照先右后左的顺序
        (*count)++;
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (!isValid(board, row, col, n)) {
            continue;
        }
        board[row][col] = 'Q';
        backtrackNQueensTotal(board, row + 1, n, count);
        board[row][col] = '.';
    }
}

int totalNQueens(int n) {
    char **board = (char **) malloc(n * sizeof(char *));
    for (int i = 0; i < n; ++i) {
        board[i] = (char *) malloc(sizeof(char) * n);
        memset(board[i], '.', sizeof(char) * n);
    }
    int count = 0;

    backtrackNQueensTotal(board, 0, n, &count);
    return count;
}

// int main() {
//     totalNQueens(4);
//     return 0;
// }

void
backtrackSubsets(int *nums, int numsSize, int *track, List *list, int startIndex, int trackSize, int columnSize[]) {
    int *newTrack = (int *) malloc(trackSize * sizeof(int));
    memcpy(newTrack, track, trackSize * sizeof(int));
    columnSize[list->size] = trackSize;
    pushBack(list, newTrack);

    for (int i = startIndex; i < numsSize; ++i) {
        track[trackSize] = nums[i];
        backtrackSubsets(nums, numsSize, track, list, i + 1, trackSize + 1, columnSize);
    }
}


int **subsets(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    List *list = createList();
    int *track = (int *) malloc(numsSize * sizeof(int));
    // C语言大数据量提交时，对内存溢出
    int columnSize[10000];
    backtrackSubsets(nums, numsSize, track, list, 0, 0, columnSize);
    *returnSize = list->size;
    *returnColumnSizes = (int *) malloc(list->size * sizeof(int));
    for (int i = 0; i < list->size; ++i) {
        (*returnColumnSizes)[i] = columnSize[i];
    }
    return list->data;
}

/*
int main() {
    int nums[] = {1, 2, 3};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;
    int **returnColumnSizes;
    int **result = subsets(nums, numsSize, &returnSize, returnColumnSizes);

    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < (*returnColumnSizes)[i]; j++) {
            printf("%d,", result[i][j]);
        }
        printf("]\n");
    }

    return 0;
}*/

void backtrackCombine(int n, int k, List *list, int *track, int startIndex, int trackSize) {
    if (trackSize == k) {
        int *newTrack = (int *) malloc(k * sizeof(int));
        memcpy(newTrack, track, k * sizeof(int));
        pushBack(list, newTrack);
    }

    for (int i = startIndex; i < n; ++i) {
        track[trackSize] = i + 1;
        backtrackCombine(n, k, list, track, i + 1, trackSize + 1);
    }
}

int **combine(int n, int k, int *returnSize, int **returnColumnSizes) {
    List *list = createList();
    int *track = (int *) malloc(n * sizeof(int));
    backtrackCombine(n, k, list, track, 0, 0);
    *returnSize = list->size;
    *returnColumnSizes = (int *) malloc(list->size * sizeof(int));
    for (int i = 0; i < list->size; ++i) {
        (*returnColumnSizes)[i] = k;
    }
    return list->data;
}


/*int main() {
    int resultSize;
    int *returnSize = &resultSize;
    int **returnColumnSizes;
    combine(4, 2, returnSize, returnColumnSizes);
}*/

typedef struct {
    int *data;
    int size;
    int capacity;
} intVector;

intVector *createIntVector() {
    intVector *list = (intVector *) malloc(sizeof(intVector));
    list->data = (int *) malloc(8 * sizeof(int));
    list->size = 0;
    list->capacity = 8;
    return list;
}

void pushBackInVector(intVector *list, int value) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->data = (int *) realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[list->size++] = value;
}


void backtrackSubsetsWithDup(int *nums, int numsSize, int *track, List *list, int startIndex, int trackSize,
                             intVector *columnSizes) {
    int *newTrack = (int *) malloc(trackSize * sizeof(int));
    memcpy(newTrack, track, trackSize * sizeof(int));
    pushBackInVector(columnSizes, trackSize);
    pushBack(list, newTrack);

    for (int i = startIndex; i < numsSize; ++i) {
        if (i > startIndex && nums[i] == nums[i - 1]) {
            continue;
        }
        track[trackSize] = nums[i];
        backtrackSubsetsWithDup(nums, numsSize, track, list, i + 1, trackSize + 1, columnSizes);
    }
}

int intAscCompare(const void *a, const void *b) {
    return *(int *) a - *(int *) b;
}

int **subsetsWithDup(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), intAscCompare);
    List *list = createList();
    int *track = (int *) malloc(numsSize * sizeof(int));
    intVector *columnSizes = createIntVector();
    backtrackSubsetsWithDup(nums, numsSize, track, list, 0, 0, columnSizes);
    *returnSize = list->size;
    *returnColumnSizes = (int *) malloc(list->size * sizeof(int));
    for (int i = 0; i < list->size; ++i) {
        (*returnColumnSizes)[i] = columnSizes->data[i];
    }
    return list->data;
}


void backtrackCombinationSum2(int *nums, int numsSize, int *track, List *list, int startIndex, int trackSize,
                              intVector *columnSizes, int combineSum, int target) {
    if (combineSum == target) {
        int *newTrack = (int *) malloc(trackSize * sizeof(int));
        memcpy(newTrack, track, trackSize * sizeof(int));
        pushBackInVector(columnSizes, trackSize);
        pushBack(list, newTrack);
        return;
    }

    if (combineSum > target) {
        return;
    }

    for (int i = startIndex; i < numsSize; ++i) {
        if (i > startIndex && nums[i] == nums[i - 1]) {
            continue;
        }
        track[trackSize] = nums[i];
        backtrackCombinationSum2(nums, numsSize, track, list, i + 1, trackSize + 1, columnSizes, combineSum + nums[i],
                                 target);
    }
}

int **combinationSum2(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), intAscCompare);
    List *list = createList();
    int *track = (int *) malloc(candidatesSize * sizeof(int));
    intVector *columnSizes = createIntVector();
    backtrackCombinationSum2(candidates, candidatesSize, track, list, 0, 0, columnSizes, 0, target);
    *returnSize = list->size;
    *returnColumnSizes = (int *) malloc(list->size * sizeof(int));
    for (int i = 0; i < list->size; ++i) {
        (*returnColumnSizes)[i] = columnSizes->data[i];
    }
    return list->data;
}

int main() {
    int resultSize;
    int *returnSize = &resultSize;
    int **returnColumnSizes;
    int candidates[] = {14, 6, 25, 9, 30, 20, 33, 34, 28, 30, 16, 12, 31, 9, 9, 12, 34, 16, 25, 32, 8, 7, 30, 12, 33,
                        20, 21, 29, 24, 17, 27, 34, 11, 17, 30, 6, 32, 21, 27, 17, 16, 8, 24, 12, 12, 28, 11, 33, 10,
                        32, 22, 13, 34, 18, 12};
    int **res = combinationSum2(candidates, 55, 27, returnSize, returnColumnSizes);
    return 0;
}

void backtrackPermuteUnique(int *nums, int numsSize, int *track, int *used, List *res, int trackSize) {
    if (trackSize == numsSize) {
        int *newTrack = (int *) malloc(numsSize * sizeof(int));
        memcpy(newTrack, track, trackSize * sizeof(int));
        pushBack(res, newTrack);
        return;
    }
    for (int i = 0; i < numsSize; ++i) {
        if (used[i] == 1 || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        used[i] = 1;
        track[trackSize] = nums[i];
        backtrackPermuteUnique(nums, numsSize, track, used, res, trackSize + 1);
        used[i] = 0;
    }
}


int **permuteUnique(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), intAscCompare);
    List *res = createList();
    int *track = (int *) malloc(numsSize * sizeof(int));
    int *used = (int *) malloc(numsSize * sizeof(int));
    memset(used, 0, numsSize * sizeof(int));
    backtrackPermuteUnique(nums, numsSize, track, used, res, 0);

    *returnSize = res->size;
    *returnColumnSizes = (int *) malloc(res->size * sizeof(int));
    for (int i = 0; i < res->size; ++i) {
// []运算符优先级比*优先级高
        (*returnColumnSizes)[i] = numsSize;
    }
    return res->data;
}

void backtrackCombinationSum(int *nums, int numsSize, intVector *track, List *list, int startIndex,
                              intVector *columnSizes, int combineSum, int target) {
    if (combineSum == target) {
        int *newTrack = (int *) malloc(track->size * sizeof(int));
        memcpy(newTrack, track->data, track->size * sizeof(int));
        pushBackInVector(columnSizes, track->size);
        pushBack(list, newTrack);
        return;
    }

    if (combineSum > target) {
        return;
    }

    for (int i = startIndex; i < numsSize; ++i) {
        pushBackInVector(track, nums[i]);
        backtrackCombinationSum(nums, numsSize, track, list, i, columnSizes, combineSum + nums[i],
                                 target);
        track->size--;
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    List *list = createList();
    intVector *track = createIntVector();
    intVector *columnSizes = createIntVector();
    backtrackCombinationSum(candidates, candidatesSize, track, list, 0, columnSizes, 0, target);
    *returnSize = list->size;
    *returnColumnSizes = (int *) malloc(list->size * sizeof(int));
    for (int i = 0; i < list->size; ++i) {
        (*returnColumnSizes)[i] = columnSizes->data[i];
    }
    return list->data;
}